
"""
 0-1 背包基础理论知识
 以下是ai写的代码，自己还不是很能理解，先暂且将dp放在这，
 后头系统的去刷一遍代码随想录
"""

weight = [2,3,4]
value = [15,20,30]

bag_size = 4

# 初始化 dp 数组
dp = [[0] * (bag_size + 1) for _ in range(len(weight))]

# 初始化第一行，当背包容量大于等于第一个物品重量时，价值为第一个物品的价值
for i in range(len(dp[0])):
    if i >= weight[0]:
        dp[0][i] = value[0]

# 填充 dp 数组
for i in range(1, len(weight)):
    for j in range(1, bag_size + 1):
        if weight[i] <= j:
            # 选择放入或不放入当前物品，取价值最大的情况
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
        else:
            # 当前物品重量大于背包容量，不放入
            dp[i][j] = dp[i - 1][j]

# 输出结果
for i in range(len(dp)):
    print(dp[i])

# 最大价值为 dp 数组最后一行最后一列的值
max_value = dp[len(weight) - 1][bag_size]
print(f"背包能装下的最大价值为: {max_value}")

